package me.mysort;

import java.util.Random;

public class A05_QuickSortDemo {
    public static void main(String[] args) {
        //快速排序
        //要用到递归的思想
        int[] arr = new int[1000000];
        Random r = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = r.nextInt();
        }
        //记录开始时间
        long start = System.currentTimeMillis();
        quickSort(arr, 0, arr.length - 1);
        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }

    //参数一：要排序的数组
    //参数二：排序数组的起始索引
    //参数三：排序数组的结束索引
    public static void quickSort(int[] arr, int i, int j) {
        //记录查找的范围
        int start = i;
        int end = j;
        //递归出口
        if (start > end) {
            return;
        }
        //记录基准数
        int baseNumber = arr[i];
        while (start != end) {
            //利用end从后往前找，找比基准数小的数字
            //一定要先移动end!
            while (true) {
                if (end <= start || arr[end] < baseNumber) {
                    break;
                }
                end--;
            }
            //利用start从前往后找，找比基准数大的数字
            while (true) {
                if (end <= start || arr[start] > baseNumber) {
                    break;
                }
                start++;
            }
            //交换元素
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
        //基准数归位
        int temp = arr[i];
        arr[i] = arr[start];
        arr[start] = temp;
        //确定6左边的范围，重复上面的步骤
        quickSort(arr, i, start - 1);
        //确定6右边的范围，重复上面的步骤
        quickSort(arr, start + 1, j);
    }
}